package 复习.博客.回溯算法_拓展;

import java.util.ArrayList;
import java.util.List;

public class 分割回文串 {

    List<List<String>> lists = new ArrayList<>();
    List<String> list = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backStacking(s,0);
        return lists;
    }

    public void backStacking(String s,int index){
        if(index == s.length()){
            lists.add(new ArrayList<>(list));
        }
        for(int i = index;i < s.length();i++){
            if(isSame(s,index,i)){
                list.add(s.substring(index,i+1));
            }else {
                continue;
            }
            backStacking(s,i + 1);
            list.remove(list.size() - 1);
        }
    }

    public boolean isSame(String s,int left,int right){
        String s1 = s.substring(left,right);;
        StringBuilder str1 = new StringBuilder(s1);
        String s2 = str1.reverse().toString();
        return s1.equals(s2);
    }
}

/*
class Solution {
    List<List<String>> resList = new ArrayList<>();//用来保存最后正确的结果
    Deque<String> myList = new LinkedList<>();//用来保存当前的结果
    public List<List<String>> partition(String s) {
        backstracking(0,s);
        return resList;
    }

    public void backstracking(int startIndex,String s){
        if(startIndex == s.length()){
            resList.add(new LinkedList<>(myList));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if(isSame(s,startIndex,i)){
                String string = s.substring(startIndex,i+1);
                myList.add(string);
            }else{
                continue;
            }
            backstracking(i + 1,s);
            myList.removeLast();
        }
    }

    public boolean isSame(String s,int start,int end){
        String tmpStr = s.substring(start, end + 1);
        StringBuilder str = new StringBuilder(tmpStr).reverse();
        return tmpStr.equals(str.toString());
    }
}
 */